package xyf.p06.sort;

import java.util.Random;

/**
 * ClassName: P0912_Sort
 * Description:
 * Author: xyf
 * Date: 9/27/22 8:12 PM
 * Version: 1.0
 **/
public class P0912_Sort
{
    //快排
    public int[] sortArray(int[] nums)
    {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int left, int right)
    {
        if (left >= right)
        {
            return;
        }

        int partition = partition(nums, left, right);

        quickSort(nums, left, partition - 1);

        quickSort(nums, partition + 1, right);
    }

    private int partition(int nums[], int left, int right)
    {
        int random = new Random().nextInt(right - left + 1) + left;

        swap(nums, random, left);

        int base = nums[left];

        int baseIndex = left;

        for (int i = left + 1; i <= right; i++)
        {
            if (nums[i] <= base)
            {
                baseIndex++;
                swap(nums, baseIndex, i);
            }
        }

        swap(nums, baseIndex, left);

        return baseIndex;
    }

    //堆排序
    public int[] sortArray2(int[] nums)
    {
        //TODO:
        return null;
    }

    private int[] tmp;

    //归并排序
    public int[] sortArray3(int[] nums)
    {
        tmp = new int[nums.length];

        mergeSort(nums, 0, nums.length - 1);

        return nums;
    }

    private void mergeSort(int[] nums, int left, int right)
    {
        if (left >= right)
        {
            return;
        }

        int mid = left + (right - left) / 2;

        mergeSort(nums, left, mid);

        mergeSort(nums, mid + 1, right);

        int indexL = left;
        int indexR = mid + 1;
        int index = 0;
        while (indexL <= mid && indexR <= right)
        {
            if (nums[indexL] <= nums[indexR])
            {
                tmp[index] = nums[indexL];
                index++;
                indexL++;
            }
            else
            {
                tmp[index] = nums[indexR];
                index++;
                indexR++;
            }
        }

        while (indexL <= mid)
        {
            tmp[index] = nums[indexL];
            index++;
            indexL++;

        }

        while (indexR <= right)
        {
            tmp[index] = nums[indexR];
            index++;
            indexR++;
        }

        for (int i = 0; i < right - left + 1; i++)
        {
            nums[left + i] = tmp[i];
        }
    }

    //冒泡排序
    public int[] sortArray4(int[] nums)
    {
        for (int i = 0; i < nums.length; i++)
        {
            for (int j = 1; j < nums.length - i; j++)
            {
                if (nums[j] < nums[j - 1])
                {
                    swap(nums, j, j - 1);
                }
            }
        }
        return nums;
    }

    private void swap(int[] nums, int i, int j)
    {
        int tmp = nums[i];

        nums[i] = nums[j];

        nums[j] = tmp;
    }
}